package algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author apple
 * @Classname SlideWindow
 * @Description 滑动窗口k个数中最大(小)数
 * 参数:{4,4,5,6,10,8,7}  k=3
 * 结果: {5,6,10,10,10}
 * @Date 2020/3/1 17:03
 */
public class SlideWindow {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(4);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(10);
        list.add(9);
        list.add(7);
        System.out.println("滑动窗口最大值");
        List<Integer> resultList = slideWindowMax(list, 3);
        resultList.forEach(x -> {
            System.out.println(x);
        });

        System.out.println("滑动窗口最小值");
        List<Integer> minResultList = slideWindowMin(list, 3);
        minResultList.forEach(x -> {
            System.out.println(x);
        });

        System.out.println("滑动窗口 链表方式");
        List<Integer> linkedListResultList = slideWindowMaxByLinkedList(list, 3);
        linkedListResultList.forEach(x -> {
            System.out.println(x);
        });
    }

    /**
     * 参数:list数组，每次k个数，取该k个数的最大值，放入结果集中。
     * 解题思路:
     * 1、读k个，组成一个大顶堆，取出对顶元素，就是该k个数中最大的数
     **/
    public static List<Integer> slideWindowMax(List<Integer> list, int k) {
        List<Integer> resultList = new ArrayList<>();
        for (int i = 0; i <= list.size() - k; i++) {
            UtilHeap maxHeap = new UtilHeap(k);
            for (int j = i; j <= i + k - 1; j++) {
                maxHeap.insertMaxHeap(maxHeap, list.get(j), 3);
            }
            resultList.add(maxHeap.getTopOfHeap(maxHeap.heapList));
        }
        return resultList;
    }

    /**
     * 滑动窗口中的最小值
     **/
    public static List<Integer> slideWindowMin(List<Integer> list, int k) {
        List<Integer> resultList = new ArrayList<>();
        for (int i = 0; i <= list.size() - k; i++) {
            UtilHeap minHeap = new UtilHeap(k);
            for (int j = i; j <= i + k - 1; j++) {
                minHeap.insertMinHeap(minHeap, list.get(j), 3);
            }
            resultList.add(minHeap.getTopOfHeap(minHeap.heapList));
        }
        return resultList;
    }

    /**
     * 使用链表求出滑动窗口中的极值
     **/
    public static List<Integer> slideWindowMaxByLinkedList(List<Integer> list, int k) {
        List<Integer> resultList = new ArrayList<>();
        LinkedList<Integer> tempLinkedList = new LinkedList<>();
        for (int i = 0; i < list.size(); i++) {
            /**链表尾端插入**/
            tempLinkedList.addLast(list.get(i));
            if (tempLinkedList.size() >= k) {
                if (tempLinkedList.size() == k + 1) {
                    /**链表长度等于k+1时，删除头部元素，保持链表中k个元素**/
                    tempLinkedList.removeFirst();
                }
                UtilHeap maxHeap = new UtilHeap(k);
                tempLinkedList.forEach(x -> {
                    maxHeap.insertMaxHeap(maxHeap, x, k);
                });
                resultList.add(maxHeap.getTopOfHeap(maxHeap.heapList));
            }
        }
        return resultList;
    }

}
